导航菜单
首页 >  全及  > 幂集

幂集

幂集幂集是一个集合中所有的子集构成的集合。

清晰吗?先来看个例子 ……

所有的子集

集 {a,b,c}:

空集 {} 是 {a,b,c} 的子集这些都是子集:{a}, {b} and {c} 这些也是子集:{a,b}, {a,c} and {b,c}全集 {a,b,c} 是 {a,b,c} 的子集

把 S={a,b,c} 所有的子集放在一起就是 {a,b,c} 的幂集

P(S) = { {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }

想象这是所有不同的方法去选择集的元素(不分次序),包括一个都不选和所有都选。

例子:冰激淋店卖香蕉、巧克力和柠檬冰激淋。

 

你有什么选择?

什么都不买(最健康!){}只买香蕉:{香蕉}。或只买 {巧克力} 或 {柠檬}或者买两种:{香蕉,巧克力} 或 {巧克力,柠檬} 或 {巧克力,柠檬}或者三种都买!(吃得了吗?){香蕉,巧克力,柠檬}

问题:如果店子也买草莓冰激淋,你会有什么选择?答案在下面。

有几个子集

简单!如果原集有 n个成员,幂集就有2n个成员

例子:在上面 {a,b,c} 的例子中,集合有三个成员(abc)。

所以幂集应该有 23 = 8个成员,这是正确的!(如上)

记法

一个集合成员的个数通常写成 |S|,所以当 S 有 n个成员时我们啊可以这样写:

|P(S)| = 2n

例子:集合 S={1,2,3,4,5} 的幂集有几个成员?

S 有 5个成员,所以:

|P(S)| = 2n = 25 = 32

下面我们会解释为什么成员的个数是 2的次方

二进制!

要建立一个集的幂集,从零开始写下有 n数位的二进制数列。数列里每一个二进制数代表一个子集,而每一个等于 "1" 的数位代表 "把对应的成员放进这个子集里"。

所以 "101" 的意思是 1 a、0 b 和 1 c,子集是 {a,c}

像这样:

 abc子集0000{ }1001{c}2010{b}3011{b,c}4100{a}5101{a,c}6110{a,b}7111{a,b,c}

次序不太漂亮,但包含了所有子集。

再一个例子

吃冰激淋!有四种口味:香蕉、巧克力、柠檬、草莓。有什么选择?

我们用英语字幕来代表四种口味:{b, c, l, s}({香蕉,巧克力,柠檬,草莓})这是一些选择:

{}(什么都不要,你在减肥){b, c, l, s} (什么都要!吃了再算){b, c}(香蕉和巧克力一起很好吃。(真的?))等等我们用 "二进制数" 来做一个列表: bcls子集00000{}10001{s}20010{l}30011{l,s}等等等等121100{b,c}131101{b,c,s}141110{b,c,l}151111{b,c,l,s}

结果是(整齐地排列):

P = { {}, {b}, {c}, {l}, {s}, {b,c}, {b,l}, {b,s}, {c,l}, {c,s}, {l,s}, {b,c,l}, {b,c,s}, {b,l,s}, {c,l,s}, {b,c,l,s} }

对称

留意在上面的列表里第一个子集是空集,最后的是全集。

第二个子集有 "s",而倒数第二个子集除了 "s" 以外,其它的都有。

  

列表上下沿中间是有某种对称的。

这是因为二进制数有漂亮优美的规律。

质数例子

幂集在很多领域都很有用。

求一个书的所有因数(不只是质因数,是所有因数)。

我可以测试所有可能答案:2、3、4、5、6、7 等等 ……

如果是大的数,这样做很花时间

但我可以质因数拼合起来吗?

510 的质因数是 2×3×5×17(用质因数工具)。

所以 510所有的因数是:

2, 3, 5 and 17,2×3, 2×5、2×17、2×3×5 and 2×3×17 ………… 就像上面的冰激淋例子,我需要幂集!

结果是:

 2,3,5,17子集510 的因数00000{ }110001{17}1720010{5}530011{5,17}5 × 17 = 8540100{3}350101{3,17}3 × 17 = 51 等等等等等等151111{2,3,5,17}2 × 3 × 5 × 17 = 510

最后答案:510 的因数是 1、2、3、5、6、10、15、17、30、34、51、85、102、170、255和510(以及 −1、−2、−3 等等)。(见 全部因数工具)。

自动化

我做了一个自动生成幂集的工具。

如果你需要幂集,去用幂集生成器。

 

  集合入门 二进制数字 对称 幂集生成器 集合索引

相关推荐: